//
// Created by weslywang on 2020/5/19.
//


#include "../common/common.h"

int ladderLength(string beginWord, string endWord, vector<string> &wordList) {
    unordered_set<string> dict(wordList.begin(), wordList.end());
    vector<string> p{beginWord};
    queue<vector<string>> paths;
    paths.push(p);
    int level = 1, minLevel = INT_MAX;
    unordered_set<string> words;
    while (!paths.empty()) {
        auto t = paths.front();
        paths.pop();
        if (t.size() > level) {
            for (string w : words) dict.erase(w);
            words.clear();
            level = t.size();
            if (level > minLevel) break;
        }
        string last = t.back();
        for (int i = 0; i < last.size(); ++i) {
            string newLast = last;
            for (char ch = 'a'; ch <= 'z'; ++ch) {
                newLast[i] = ch;
                if (!dict.count(newLast)) continue;
                words.insert(newLast);
                vector<string> nextPath = t;
                nextPath.push_back(newLast);
                if (newLast == endWord) {
                    minLevel = level;
                    return minLevel + 1;
                } else paths.push(nextPath);
            }
        }
    }
    return 0;
}

int main() {
    struct timeval start;
    struct timeval end;
    unsigned long timer;

    Common common;
    int a[] = {1, 2, 3, 4, 5};
    vector<vector<string>> numList = common.loadStringData();
    for (int i = 0; i < numList.size(); i++) {
        gettimeofday(&start, NULL);

//        auto index = find(numList[i].begin(), numList[i].end(), "grind1");
//        if (index != numList[i].end()) {
//            cout << "找到了" << endl;
//        }
//        cout<<index<<endl;

//        printVector(findLadders("qa", "sq", numList[i]));
        cout << (ladderLength("a", "c", numList[i])) << endl;
//        printVector(findLadders("hit", "cog", numList[i]));
//        printVector(findLadders("hot", "dog", numList[i]));
//        printVector(findLadders("cet", "ism", numList[i]));
//        printVector(findLadders("sand", "acne", numList[i]));
//        cout << ladderLength("nanny", "aloud", numList[i]) << endl;

        gettimeofday(&end, NULL);
        timer = 1000000 * (end.tv_sec - start.tv_sec) + end.tv_usec - start.tv_usec;
        cout << timer / 1000 << "毫秒" << endl;
        cout << "**************" << endl;
    }
    return 0;
}